package 中等.搜索.广度优先搜索;

import java.util.*;

/**
 * 有 n 个人，每个人都有一个  0 到 n-1 的唯一 id 。
 * 给你数组 watchedVideos  和 friends ，其中 watchedVideos[i]  和 friends[i] 分别表示
 *  id = i 的人观看过的视频列表和他的好友列表。
 * Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看
 * 过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好
 * 友观看过的视频。
 * 给定你的 id  和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升
 * 序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/get-watched-videos-by-your-friends
 */
public class 获取你好友已观看的视频_1311 {

    public static void main(String[] args) {

    }

    /**
     * 广度优先搜索+哈希表
     * 1，先通过 广度优先搜索 找到 level 等级的朋友 id 集合,
     * 搜索过程中需要去重，访问过的朋友不再访问
     * 2，然后通过哈希表统计每个视频出现的次数
     * 3，排序
     */
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        List<String> list = new ArrayList<>();
        boolean[] visited = new boolean[friends.length];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(id);
        visited[id] = true;

        while (level-- > 0) {
            int size = queue.size();
            while (size-- > 0) {
                for (int next : friends[queue.pollFirst()]) {
                    if (!visited[next]) {
                        queue.addLast(next);
                        visited[next] = true;
                    }
                }
            }
        }

        Map<String, Integer> map = new HashMap<>();
        while (!queue.isEmpty()) {
            for (String video : watchedVideos.get(queue.pollFirst())) {
                map.put(video, map.getOrDefault(video, 0) + 1);
            }
        }
        List<String[]> lists = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            lists.add(new String[]{entry.getKey(), entry.getValue() + ""});
        }
        lists.sort((a, b) -> Integer.valueOf(a[1]) == Integer.valueOf(b[1]) ?
                a[0].compareTo(b[0]) :
                Integer.valueOf(a[1]) - Integer.valueOf(b[1]));

        for (String[] strings : lists) {
            list.add(strings[0]);
        }
        return list;
    }

}
